﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
		<title>Recherche A*</title>
		<link rel="stylesheet" type="text/css" href="style.css" />
	</head>
	<body class="twoColFixLtHdr">
    <div id="container">
		<div id="header">Algorithme de recherche de chemin A*</div>

		<div id="menu">
			<ul>
				<li><a href="index.html">Accueil</a></li>
				<li><a href="presentation.html">Présentation</a></li>
				<li><a href="connaissances.html">Connaissances</a></li>
				<li><a href="demarche.html">Démarche</a></li>
				<li><a href="difficultes.html">Difficultés</a></li>
				<li><a href="analyse.html">Analyse</a></li>
				<li><a href="conclusion.html">Conclusion</a></li>
				<li><a href="bibliographie.html">Bibliographie</a></li>
				<li><a href="glossaire.html">Glossaire</a></li>
				<li><a href="telechargement.html">Téléchargement</a></li>
			</ul>
		</div>

		<div id="content"><br />
			<h1>Conclusion</h1><br /><br />
			Nous avons atteint le premier but de notre expérimentation, c'est-à-dire programmer une implémentation du A* qui soit fonctionnelle. Nous avons ainsi réalisé un prototype console à cet effet. Cependant, nous n'avons pas atteint le deuxième but qui était d'implémenter une optimisation fonctionnelle et efficace de l'algorithme qui pourrait être utilisée dans les jeux. Notre prototype graphique est fonctionnel et conforme à nos idées, il fait ce que l'on attend de lui, mais il ne constitue pas une version optimisée du A* qui pourrait être utilisée dans une situation de jeu, ou tout autre où il y aurait une grande aire de recherche. Notre hypothèse de départ était donc fausse.<br /><br />
            Mais malgré cela, nous avons tout de même exploré et approfondi une facette importante de l'algorithme.<br /><br />
            Comme nous l'avons déjà mentionné, les compagnies de jeux vidéo adoptent une optimisation "maison" de l'algorithme et ne dévoilent pas vraiment leurs solutions. Avec ce manque de clarté sur ce qui est vraiment utilisé, nous avons choisi d'optimiser le A* en utilisant "les points visibles", d'une façon que nous croyions avantageuse. Nous avons eu tort.<br /><br />
            Nous avons cependant croisé, au cours de nos recherches, d'autres pistes de solutions intéressantes, dont une principalement que nous croyons qui soit l'approche traditionnellement utilisée pour optimiser l'algorithme. Il s'agit du A* hiérarchique, sur lequel l'aire de recherche est divisée en zones de plus en plus grandes selon les niveaux de recherche. Ainsi, pour se déplacer dans une aire de 1000 x 1000 par exemple, le personnage trouve la sortie vers l'extérieur du carré 10 x 10 dans lequel il se situe puis effectue une recherche sur 100 x 100 carrés de 10 x 10 chacuns. L'aire de recherche est donc beaucoup moins grande, 100 x 100 au lieu de 1000 x 1000. Pourquoi n'avions nous pas pris cette méthode, direz-vous ? Parce que lorsque nous avons pris la décision quant à l'optimisation du A* que nous allions implémenter, nous ne connaissions pas les avantages de cette méthode par rapport à la nôtre. Même si nous aurions sû, cette méthode (le A* hiérarchique) demeure nettement plus compliqué à implémenter.
            </div>
		<br class="clearfloat" />
		<div id="footer"><br /><p align="center">Par Benoît Tremblay et François Roseberry</p></div>
    </div>
	</body>
</html>